CS5303 – Design and Analysis of Algorithms

import time
import random
import sys

def interpolation_search(arr, target):
    """
    Interpolation Search Algorithm (Understandable Step-by-Step Implementation)
    - Prerequisite: Array MUST be sorted; works best on uniformly distributed data.
    - Probe Formula: pos = low + ((target - arr[low]) * (high - low)) // (arr[high] - arr[low])
    """
    low, high = 0, len(arr) - 1
    comparisons = 0

    # Continue search only while target is bounded by current window
    while low <= high and arr[low] <= target <= arr[high]:
        comparisons += 1

        # Check edge case: single element interval
        if low == high:
            if arr[low] == target:
                return low, comparisons
            return -1, comparisons

        # --- STEP 1: Calculate estimated probe position ---
        # Instead of fixed midpoint, estimate index proportional to value difference
        pos = low + int(((target - arr[low]) * (high - low)) / (arr[high] - arr[low]))

        # --- STEP 2: Compare target with estimated element ---
        if arr[pos] == target:
            return pos, comparisons         # Element found at estimated probe!
        elif arr[pos] < target:
            low = pos + 1                   # Target is greater; search right sub-array
        else:
            high = pos - 1                  # Target is smaller; search left sub-array

    return -1, comparisons                 # Element not found

def binary_search(arr, target):
    """Standard Binary Search for empirical comparison"""
    low, high = 0, len(arr) - 1
    comparisons = 0
    while low <= high:
        comparisons += 1
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid, comparisons
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1, comparisons

def performance_analysis():
    sizes = [1000, 5000, 10000, 50000, 100000]
    print(f"{'Size':>10} {'IS Time(ms)':>14} {'BS Time(ms)':>14} {'IS Comparisons':>16} {'BS Comparisons':>16}")
    print('-' * 75)
    for size in sizes:
        arr = sorted(random.sample(range(size * 10), size))
        target = arr[random.randint(0, size - 1)]
        # Measure Interpolation Search timing
        start = time.perf_counter()
        for _ in range(100):
            idx_is, comp_is = interpolation_search(arr, target)
        is_time = (time.perf_counter() - start) / 100 * 1000
        # Measure Binary Search timing
        start = time.perf_counter()
        for _ in range(100):
            idx_bs, comp_bs = binary_search(arr, target)
        bs_time = (time.perf_counter() - start) / 100 * 1000
        print(f"{size:>10} {is_time:>14.4f} {bs_time:>14.4f} {comp_is:>16} {comp_bs:>16}")

# --- Main Demonstration ---
arr = [2, 5, 10, 15, 23, 35, 48, 60, 75, 90, 105, 120]
target = 35
idx, comps = interpolation_search(arr, target)
print(f"Array: {arr}")
print(f"Searching for: {target}")
print(f"Found at index: {idx}, Comparisons: {comps}")
print()
performance_analysis()

import time
import random
import string

# =====================================================================
# 1. NAIVE BRUTE-FORCE STRING MATCHING
# Slides pattern window 1 char at a time; compares chars until mismatch.
# =====================================================================
def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    matches, comparisons = [], 0

    for i in range(n - m + 1):
        j = 0
        while j < m:
            comparisons += 1
            if text[i + j] != pattern[j]:
                break  # Mismatch: slide window by 1
            j += 1
        if j == m:
            matches.append(i)  # Full match found!
    return matches, comparisons

# =====================================================================
# 2. KNUTH-MORRIS-PRATT (KMP) ALGORITHM
# Avoids re-evaluating text chars by using Longest Prefix Suffix (LPS).
# =====================================================================
def compute_lps(pattern):
    """Computes LPS array: length of longest proper prefix that is also suffix"""
    m = len(pattern)
    lps = [0] * m
    length, i = 0, 1

    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length != 0:
            length = lps[length - 1]  # Fallback to previous longest prefix
        else:
            lps[i] = 0
            i += 1
    return lps

def kmp_search(text, pattern):
    n, m = len(text), len(pattern)
    lps = compute_lps(pattern)  # Preprocessing Step: O(m)
    matches, comparisons = [], 0
    i = j = 0  # i: text pointer, j: pattern pointer

    while i < n:
        comparisons += 1
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == m:
            matches.append(i - j)      # Pattern detected at index i - j
            j = lps[j - 1]             # Jump pattern pointer based on LPS
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]         # Don't increment i; shift pattern pointer
            else:
                i += 1                 # Move text pointer forward
    return matches, comparisons

# =====================================================================
# 3. RABIN-KARP ROLLING HASH ALGORITHM
# Hashes the pattern and sliding windows; checks chars only on hash match.
# =====================================================================
def rabin_karp(text, pattern, q=101):
    n, m = len(text), len(pattern)
    d = 256  # Size of alphabet (ASCII)
    h = pow(d, m - 1, q)  # Multiplier factor d^(m-1) % q
    p_hash = t_hash = 0
    matches, comparisons = [], 0

    # Step 1: Calculate initial hash of pattern and first text window
    for i in range(m):
        p_hash = (d * p_hash + ord(pattern[i])) % q
        t_hash = (d * t_hash + ord(text[i])) % q

    # Step 2: Slide window over text
    for s in range(n - m + 1):
        # Step 2.1: Check if hashes match (candidate match)
        if p_hash == t_hash:
            for k in range(m):
                comparisons += 1
                if text[s + k] != pattern[k]:
                    break
            else:
                matches.append(s)  # Genuine match confirmed!

        # Step 2.2: Compute rolling hash for next window in O(1)
        if s < n - m:
            t_hash = (d * (t_hash - ord(text[s]) * h) + ord(text[s + m])) % q
            if t_hash < 0:
                t_hash += q
    return matches, comparisons

# --- Main Demonstration ---
text = 'AABAACAADAABAABA'
pattern = 'AABA'
print(f'Text: {text}')
print(f'Pattern: {pattern}')
m1, c1 = naive_search(text, pattern)
m2, c2 = kmp_search(text, pattern)
m3, c3 = rabin_karp(text, pattern)
print(f'\nNaive -> Matches at: {m1}, Comparisons: {c1}')
print(f'KMP   -> Matches at: {m2}, Comparisons: {c2}')
print(f'RK    -> Matches at: {m3}, Comparisons: {c3}')

# Benchmark performance on large randomized text
text_large = ''.join(random.choices('ABCD', k=10000))
patterns = ['AB', 'ABCD', 'ABCDAB', 'ABCDABCD']
print(f'\n{"Pattern":>12} {"Naive":>10} {"KMP":>10} {"RK":>10}')
print('-' * 50)
for p in patterns:
    _, c1 = naive_search(text_large, p)
    _, c2 = kmp_search(text_large, p)
    _, c3 = rabin_karp(text_large, p)
    print(f'{p:>12} {c1:>10} {c2:>10} {c3:>10}')

import heapq

# =====================================================================
# 1. UNION-FIND (DISJOINT SET UNION) DATA STRUCTURE FOR KRUSKAL
# Uses Path Compression + Union by Rank for near-constant O(alpha(V)) time.
# =====================================================================
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # Each node is initially its own parent
        self.rank = [0] * n           # Depth estimation for balancing trees

    def find(self, x):
        """Find root representative with Path Compression"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Flattens tree
        return self.parent[x]

    def union(self, x, y):
        """Union two sets by rank. Returns False if already in same set (cycle)."""
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False  # Cycle detected! Do not add this edge.

        # Attach smaller rank tree under root of higher rank tree
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

# =====================================================================
# 2. KRUSKAL'S ALGORITHM
# Sorts all edges globally, then greedily selects lightest non-cycle edges.
# =====================================================================
def kruskal(n, edges):
    """edges: list of tuples (weight, u, v)"""
    edges.sort()  # Step 1: Sort all edges globally in O(E log E)
    uf = UnionFind(n)
    mst = []
    cost = 0

    # Step 2: Iterate through sorted edges
    for w, u, v in edges:
        if uf.union(u, v):          # If u and v belong to different components
            mst.append((u, v, w))   # Add edge to MST
            cost += w
        if len(mst) == n - 1:       # An MST always has exactly V - 1 edges
            break
    return mst, cost

# =====================================================================
# 3. PRIM'S ALGORITHM
# Starts from an arbitrary vertex; grows tree greedily using Min-Heap.
# =====================================================================
def prim(n, adj, start=0):
    """adj: adjacency list dictionary {u: [(v, weight), ...]}"""
    INF = float('inf')
    key = [INF] * n          # Minimum weight to connect vertex v to current tree
    parent = [-1] * n        # Parent pointer in MST
    inMST = [False] * n      # Track visited vertices in the growing tree
    key[start] = 0
    pq = [(0, start)]        # Min-heap priority queue stores (key, vertex)
    mst = []
    cost = 0

    while pq:
        # Step 1: Extract vertex with minimum key
        w, u = heapq.heappop(pq)
        if inMST[u]:
            continue
        inMST[u] = True

        if parent[u] != -1:
            mst.append((parent[u], u, w))
            cost += w

        # Step 2: Relax neighboring cut edges
        for v, wt in adj.get(u, []):
            if not inMST[v] and wt < key[v]:
                key[v] = wt
                parent[v] = u
                heapq.heappush(pq, (wt, v))

    return mst, cost

# --- Graph Definition (7 vertices, 11 edges) ---
n = 7
edges = [
    (7, 0, 1), (5, 0, 3), (8, 1, 2), (9, 1, 3),
    (7, 1, 4), (5, 2, 4), (15, 3, 4), (6, 3, 5),
    (8, 4, 5), (9, 4, 6), (11, 5, 6)
]

adj = {}
for w, u, v in edges:
    adj.setdefault(u, []).append((v, w))
    adj.setdefault(v, []).append((u, w))

k_mst, k_cost = kruskal(n, edges[:])
p_mst, p_cost = prim(n, adj)

print("=== Kruskal's MST ===")
for u, v, w in k_mst:
    print(f' Edge ({u} - {v}) Weight: {w}')
print(f' Total MST Cost: {k_cost}')

print("\n=== Prim's MST ===")
for u, v, w in p_mst:
    print(f' Edge ({u} - {v}) Weight: {w}')
print(f' Total MST Cost: {p_cost}')

import heapq

def dijkstra(graph, source):
    """
    Dijkstra's Single-Source Shortest Path using Binary Min-Heap
    - Requires: Non-negative edge weights (w >= 0).
    - graph: Adjacency list dictionary {u: [(v, weight), ...]}
    """
    n = len(graph)
    dist = [float('inf')] * n   # Shortest distances from source
    prev = [None] * n           # Parent pointers for path reconstruction
    dist[source] = 0

    # Min-Heap stores tuples of (tentative_distance, vertex)
    pq = [(0, source)]
    visited = set()

    while pq:
        # --- STEP 1: Extract settled vertex with lowest distance ---
        d, u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)

        # --- STEP 2: Relax each outgoing adjacent edge (u -> v) ---
        for v, w in graph[u]:
            # Edge relaxation condition
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w   # Shorter route discovered!
                prev[v] = u             # Record u as predecessor of v
                heapq.heappush(pq, (dist[v], v))

    return dist, prev

def reconstruct_path(prev, source, target):
    """Backtracks through parent array prev to reassemble the exact route"""
    path = []
    node = target
    while node is not None:
        path.append(node)
        node = prev[node]
    path.reverse()  # Reverse to get order: source -> ... -> target
    if path and path[0] == source:
        return path
    return []

# --- Graph Definition (Adjacency List) ---
# Vertices 0 to 5, directed weighted edges
graph = {
    0: [(1, 4), (2, 1)],
    1: [(3, 1)],
    2: [(1, 2), (3, 5)],
    3: [(4, 3)],
    4: [(5, 2)],
    5: []
}

source = 0
dist, prev = dijkstra(graph, source)

print(f'Shortest paths from vertex {source}:')
print(f'{"Vertex":>8} {"Distance":>10} {"Path":>30}')
print('-' * 55)
for v in range(len(graph)):
    path = reconstruct_path(prev, source, v)
    path_str = ' -> '.join(map(str, path)) if path else 'No path'
    d = dist[v] if dist[v] != float('inf') else 'INF'
    print(f'{v:>8} {str(d):>10} {path_str:>30}')

import random

comparison_count = 0  # Global counter to track elemental comparisons

def min_max_dc(arr, low, high):
    """
    Finds (min, max) using Divide and Conquer.
    Recurrence: T(n) = 2T(n/2) + 2 comparisons
    Total comparisons: 3n/2 - 2 (for n power of 2)
    """
    global comparison_count
    
    # --- Step 1: Base Case: Single element array ---
    if low == high:
        return arr[low], arr[low]
        
    # --- Step 2: Base Case: Two element subarray (1 comparison) ---
    if high == low + 1:
        comparison_count += 1
        if arr[low] < arr[high]:
            return arr[low], arr[high]
        return arr[high], arr[low]
        
    # --- Step 3: Divide into two halves ---
    mid = (low + high) // 2
    lmin, lmax = min_max_dc(arr, low, mid)
    rmin, rmax = min_max_dc(arr, mid + 1, high)
    
    # --- Step 4: Combine subproblem results (2 comparisons) ---
    comparison_count += 1
    overall_min = lmin if lmin < rmin else rmin
    
    comparison_count += 1
    overall_max = lmax if lmax > rmax else rmax
    
    return overall_min, overall_max

def min_max_naive(arr):
    """
    Standard linear scan finding min and max.
    Requires 2*(n-1) comparisons in worst case.
    """
    mn, mx = arr[0], arr[0]
    comps = 0
    for x in arr[1:]:
        comps += 1
        if x < mn: 
            mn = x
        comps += 1
        if x > mx: 
            mx = x
    return mn, mx, comps

# --- Demonstration on sample array ---
arr = [3, 1, 7, 4, 9, 2, 8, 5, 6, 0]
comparison_count = 0
mn, mx = min_max_dc(arr, 0, len(arr) - 1)
dc_comps = comparison_count
_, _, naive_comps = min_max_naive(arr)

print(f'Array: {arr}')
print(f'Min: {mn}, Max: {mx}')
print(f'D&C Comparisons: {dc_comps}')
print(f'Naive Comparisons: {naive_comps}')

# --- Performance Analysis across various input sizes ---
print(f'\n{"Size":>8} {"DC Comps":>12} {"Naive Comps":>14} {"Formula 3n/2-2":>16}')
print('-' * 56)
for size in [10, 100, 1000, 10000]:
    test_arr = [random.randint(1, 10000) for _ in range(size)]
    comparison_count = 0
    mn, mx = min_max_dc(test_arr, 0, len(test_arr) - 1)
    dc = comparison_count
    _, _, naive = min_max_naive(test_arr)
    formula = 3 * size // 2 - 2
    print(f'{size:>8} {dc:>12} {naive:>14} {formula:>16}')

def matrix_chain_order(dims):
    """
    Computes optimal matrix chain multiplication order using Dynamic Programming.
    dims: list of dimensions where matrix A_i has dimension dims[i-1] x dims[i]
    Time Complexity:  O(n^3)
    Space Complexity: O(n^2) for memoization tables
    """
    n = len(dims) - 1
    
    # Step 1: Initialize DP cost table m and split table s
    # m[i][j] stores minimum scalar multiplications needed for A_i..A_j
    # s[i][j] stores the optimal split index k that achieves m[i][j]
    m = [[0] * (n + 1) for _ in range(n + 1)]
    s = [[0] * (n + 1) for _ in range(n + 1)]
    
    # Step 2: Iterate through subchain lengths l from 2 to n
    for l in range(2, n + 1):
        for i in range(1, n - l + 2):
            j = i + l - 1
            m[i][j] = float('inf')
            
            # Step 3: Evaluate all potential split points k
            for k in range(i, j):
                # Cost = left subchain cost + right subchain cost + cost of multiplying results
                cost = m[i][k] + m[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
                if cost < m[i][j]:
                    m[i][j] = cost
                    s[i][j] = k  # Store optimal split
                    
    return m, s

def print_optimal_parens(s, i, j):
    """Recursively reconstructs the parenthesized multiplication sequence."""
    if i == j:
        return f'A{i}'
    k = s[i][j]
    left = print_optimal_parens(s, i, k)
    right = print_optimal_parens(s, k + 1, j)
    return f'({left} x {right})'

def print_dp_table(m, n):
    """Displays formatted DP cost matrix."""
    print('\nDP Cost Table m[i][j]:')
    print(f'{"":>6}', end='')
    for j in range(1, n + 1):
        print(f'A{j:>8}', end='')
    print()
    for i in range(1, n + 1):
        print(f'A{i:<5}', end='')
        for j in range(1, n + 1):
            if j < i: 
                print(f'{"---":>9}', end='')
            else: 
                print(f'{m[i][j]:>9}', end='')
        print()

# --- Problem Instance: A1(10x30), A2(30x5), A3(5x60), A4(60x10) ---
dims = [10, 30, 5, 60, 10]
n = len(dims) - 1

print('Matrix Dimensions:')
for i in range(n):
    print(f' A{i+1}: {dims[i]} x {dims[i+1]}')

m, s = matrix_chain_order(dims)
print(f'\nMinimum scalar multiplications: {m[1][n]}')
print(f'Optimal parenthesization: {print_optimal_parens(s, 1, n)}')
print_dp_table(m, n)

def is_safe(board, row, col):
    """
    Checks if a queen can be safely placed at (row, col).
    Verifies that no previous queen shares the same column or diagonal.
    """
    for prev_row in range(row):
        placed = board[prev_row]
        # Column conflict check
        if placed == col:
            return False
        # Diagonal conflict check (|row1 - row2| == |col1 - col2|)
        if abs(prev_row - row) == abs(placed - col):
            return False
    return True

def solve_n_queens(n):
    """
    Solves N-Queens problem using Backtracking (Depth-First State Space Search).
    Returns list of all valid configurations and total backtracks executed.
    """
    board = [-1] * n  # board[r] stores column index for queen in row r
    solutions = []
    backtrack_count = [0]

    def backtrack(row):
        # Step 1: Base case - All n rows successfully placed
        if row == n:
            solutions.append(board[:])
            return
            
        # Step 2: Try placing queen in each column of current row
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col           # Choose
                backtrack(row + 1)         # Explore
                board[row] = -1            # Un-choose (Backtrack)
                
        # Count dead-end backtrack events
        backtrack_count[0] += 1

    backtrack(0)
    return solutions, backtrack_count[0]

def display_board(solution, n):
    """Visualizes chessboard with placed Queens (Q) and empty cells (.)."""
    print(' +' + '---+' * n)
    for row in range(n):
        print(' |', end='')
        for col in range(n):
            if solution[row] == col:
                print(' Q |', end='')
            else:
                print(' . |', end='')
        print()
        print(' +' + '---+' * n)

# --- Solve for N=4 (show all configurations) and N=6, N=8 (solution counts) ---
for n in [4, 6, 8]:
    solutions, backtracks = solve_n_queens(n)
    print(f'N={n}: {len(solutions)} solutions, {backtracks} backtracks')
    if n == 4:
        print(f'\n All solutions for {n}-Queens:')
        for i, sol in enumerate(solutions, 1):
            print(f'\n Solution {i}: {sol}')
            display_board(sol, n)

import heapq
from itertools import permutations

INF = float('inf')

def reduce_matrix(mat):
    """
    Computes lower bound reduction for TSP cost matrix.
    Subtracts row minimums and column minimums to produce reduced cost matrix.
    Sum of reductions provides rigorous lower bound on any tour in this branch.
    """
    m = [row[:] for row in mat]
    n = len(m)
    cost = 0
    
    # Step 1: Row reduction
    for i in range(n):
        row_min = min(m[i])
        if row_min and row_min != INF:
            cost += row_min
            m[i] = [x - row_min if x != INF else INF for x in m[i]]
            
    # Step 2: Column reduction
    for j in range(n):
        col_min = min(m[i][j] for i in range(n))
        if col_min and col_min != INF:
            cost += col_min
            for i in range(n):
                if m[i][j] != INF:
                    m[i][j] -= col_min
                    
    return m, cost

def tsp_brute_force(cost, n):
    """
    Finds exact optimal TSP Hamiltonian cycle via permutation search.
    Provides ground-truth validation for Branch and Bound.
    """
    cities = list(range(1, n))
    best_cost = INF
    best_path = None
    for perm in permutations(cities):
        path = [0] + list(perm) + [0]
        c = sum(cost[path[i]][path[i+1]] for i in range(n))
        if c < best_cost:
            best_cost = c
            best_path = path
    return best_path, best_cost

# --- 5-city cost matrix definition ---
cost = [
    [INF, 10,  8,  9,  7],
    [ 10, INF, 10,  5,  6],
    [  8, 10, INF,  8,  9],
    [  9,  5,  8, INF,  6],
    [  7,  6,  9,  6, INF]
]
n = 5
cities = ['A', 'B', 'C', 'D', 'E']

best_path, best_cost = tsp_brute_force(cost, n)

print('5-City TSP - Cost Matrix:')
print(f'{"":>4}', ' '.join(f'{c:>5}' for c in cities))
for i, row in enumerate(cost):
    r = ['INF' if x == INF else str(x) for x in row]
    print(f'{cities[i]:>4}', ' '.join(f'{v:>5}' for v in r))

print(f'\nOptimal Tour: {" -> ".join(cities[i] for i in best_path)}')
print(f'Minimum Cost: {best_cost}')
print(f'\nPath verification:')
for i in range(n):
    u, v = best_path[i], best_path[i+1]
    print(f' {cities[u]} -> {cities[v]}: cost = {cost[u][v]}')

def first_fit(items, capacity=1.0):
    """
    First Fit (FF) Approximation:
    Places each item into the first bin with sufficient remaining space.
    Time Complexity: O(n^2) naive, O(n log n) with balanced search tree.
    """
    bins = []          # Tracks remaining capacity in each bin
    bin_contents = []  # Stores item lists for each bin
    
    for item in items:
        placed = False
        # Search for first bin with enough headroom
        for i, space in enumerate(bins):
            if space >= item:
                bins[i] -= item
                bin_contents[i].append(item)
                placed = True
                break
        # No existing bin has room: open new bin
        if not placed:
            bins.append(capacity - item)
            bin_contents.append([item])
            
    return bin_contents

def first_fit_decreasing(items, capacity=1.0):
    """
    First Fit Decreasing (FFD) Approximation:
    Pre-sorts items in non-increasing order, then applies First Fit.
    Guaranteed: Bins <= (11/9)*OPT + 6/9
    """
    return first_fit(sorted(items, reverse=True), capacity)

def best_fit_decreasing(items, capacity=1.0):
    """
    Best Fit Decreasing (BFD) Approximation:
    Sorts descending, then places each item into the tightest fitting bin
    (minimizing leftover space in that bin).
    """
    sorted_items = sorted(items, reverse=True)
    bins = []
    bin_contents = []
    
    for item in sorted_items:
        best_idx = -1
        best_space = float('inf')
        # Find bin that leaves minimum leftover space
        for i, space in enumerate(bins):
            if space >= item and (space - item) < best_space:
                best_space = space - item
                best_idx = i
        if best_idx >= 0:
            bins[best_idx] -= item
            bin_contents[best_idx].append(item)
        else:
            bins.append(capacity - item)
            bin_contents.append([item])
            
    return bin_contents

def display_bins(label, bins):
    """Displays packed bins and their percentage utilization bar."""
    print(f'\n{label}: {len(bins)} bins')
    for i, b in enumerate(bins, 1):
        used = sum(b)
        bar = '#' * int(used * 20)
        print(f' Bin {i}: {[round(x,1) for x in b]} | Used: {used:.1f} [{bar:<20}]')

# --- Problem Instance Definition ---
items = [0.5, 0.7, 0.3, 0.9, 0.2, 0.6, 0.8, 0.4, 0.1, 0.5]
capacity = 1.0
lower_bound = -(-sum(items) // capacity)  # Theoretical lower bound = ceil(sum/cap)

print(f'Items: {items}')
print(f'Capacity: {capacity}')
print(f'Sum of items: {sum(items)}')
print(f'Lower bound on bins: {int(lower_bound)}')

ff_bins = first_fit(items)
ffd_bins = first_fit_decreasing(items)
bfd_bins = best_fit_decreasing(items)

display_bins('First Fit (FF)', ff_bins)
display_bins('First Fit Decreasing (FFD)', ffd_bins)
display_bins('Best Fit Decreasing (BFD)', bfd_bins)

print(f'\nSummary: Lower Bound={int(lower_bound)}, FF={len(ff_bins)}, FFD={len(ffd_bins)}, BFD={len(bfd_bins)}')

import random
import time
import sys

sys.setrecursionlimit(20000)
comparisons = 0  # Global counter to track elemental comparisons

def partition(arr, low, high):
    """
    Standard Lomuto partitioning scheme:
    Places pivot arr[high] at its correct sorted position.
    Elements <= pivot are moved to left; elements > pivot moved to right.
    """
    global comparisons
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        comparisons += 1
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def deterministic_quicksort(arr, low, high):
    """Deterministic Quick Sort: Always uses arr[high] as pivot."""
    if low < high:
        pi = partition(arr, low, high)
        deterministic_quicksort(arr, low, pi - 1)
        deterministic_quicksort(arr, pi + 1, high)

def randomized_quicksort(arr, low, high):
    """
    Randomized Quick Sort: Selects a pivot uniformly at random from arr[low..high],
    swapping it to high before calling partition.
    Guarantees expected O(n log n) time on all input distributions.
    """
    if low < high:
        # Step 1: Select uniform random pivot index and swap to end
        rand_idx = random.randint(low, high)
        arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
        
        # Step 2: Standard partition and recursive conquer
        pi = partition(arr, low, high)
        randomized_quicksort(arr, low, pi - 1)
        randomized_quicksort(arr, pi + 1, high)

def run_test(name, sort_fn, arr):
    """Helper function to execute sort and return comparison count and duration."""
    global comparisons
    a = arr[:]
    comparisons = 0
    start = time.perf_counter()
    sort_fn(a, 0, len(a) - 1)
    elapsed = (time.perf_counter() - start) * 1000
    return comparisons, elapsed

# --- Benchmark Suite (N = 5000 elements across 4 input configurations) ---
N = 5000
test_cases = {
    'Random'       : [random.randint(1, 100000) for _ in range(N)],
    'Sorted'       : list(range(N)),
    'Reverse'      : list(range(N, 0, -1)),
    'Nearly Sorted': list(range(N))
}

# Add 5% random perturbations to Nearly Sorted array
ns = test_cases['Nearly Sorted']
for _ in range(N // 20):
    i, j = random.randint(0, N-1), random.randint(0, N-1)
    ns[i], ns[j] = ns[j], ns[i]

print(f"{'Input Type':<16} {'DQS Comps':>12} {'DQS Time(ms)':>14} {'RQS Comps':>12} {'RQS Time(ms)':>14}")
print('-' * 72)
for case, arr in test_cases.items():
    d_comps, d_time = run_test('DQS', deterministic_quicksort, arr)
    r_comps, r_time = run_test('RQS', randomized_quicksort, arr)
    print(f'{case:<16} {d_comps:>12} {d_time:>14.2f} {r_comps:>12} {r_time:>14.2f}')